package cn.zifangsky.graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 测试图相关逻辑
 *
 * @author zifangsky
 * @date 2019/1/22
 * @since 1.0.0
 */
public class TestGraph {

    /**
     * 测试使用邻接矩阵构建图
     */
    @Test
    public void testForEach(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("A", "D"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("C", "A"));
        weightList.add(new Edge("C", "D"));

        GraphMatrix graphMatrix = new GraphMatrix(vertexArray, weightList, true);

        graphMatrix.foreach((startVertex, endVertex) -> {
            System.out.println(startVertex + " --> " + endVertex);
        });

    }


    /**
     * 测试DFS（深度优先）搜索
     */
    @Test
    public void testDFS(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G", "H"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("B", "H"));
        weightList.add(new Edge("C", "D"));
        weightList.add(new Edge("C", "E"));
        weightList.add(new Edge("E", "F"));
        weightList.add(new Edge("E", "G"));
        weightList.add(new Edge("E", "H"));

        GraphMatrix graphMatrix = new GraphMatrix(vertexArray, weightList);

        graphMatrix.dfsForeach(vertex -> System.out.print(vertex + " "));
    }

    /**
     * 测试BFS（宽度优先）搜索
     */
    @Test
    public void testBFS(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G", "H"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("B", "H"));
        weightList.add(new Edge("C", "D"));
        weightList.add(new Edge("C", "E"));
        weightList.add(new Edge("E", "F"));
        weightList.add(new Edge("E", "G"));
        weightList.add(new Edge("E", "H"));

        GraphMatrix graphMatrix = new GraphMatrix(vertexArray, weightList);

        graphMatrix.bfsForeach(vertex -> System.out.print(vertex + " "));
    }

    /* 基于邻接表的测试用例 */

    /**
     * 测试使用邻接表构建图
     */
    @Test
    public void testInitGraphList(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("A", "D"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("C", "A"));
        weightList.add(new Edge("C", "D"));

        GraphList graphList = new GraphList(vertexArray, weightList, true);

        graphList.foreach(System.out::println);
    }

    /**
     * 测试使用邻接表的 深度优先 搜索
     */
    @Test
    public void testGraphListDFS(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G", "H"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("B", "H"));
        weightList.add(new Edge("C", "D"));
        weightList.add(new Edge("C", "E"));
        weightList.add(new Edge("E", "F"));
        weightList.add(new Edge("E", "G"));
        weightList.add(new Edge("E", "H"));

        GraphList graphList = new GraphList(vertexArray, weightList);

        graphList.dfsForeach(vertex -> System.out.print(vertex + " "));
    }

    /**
     * 测试使用邻接表的 宽度优先 搜索
     */
    @Test
    public void testGraphListBFS(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G", "H"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("B", "H"));
        weightList.add(new Edge("C", "D"));
        weightList.add(new Edge("C", "E"));
        weightList.add(new Edge("E", "F"));
        weightList.add(new Edge("E", "G"));
        weightList.add(new Edge("E", "H"));

        GraphList graphList = new GraphList(vertexArray, weightList);

        graphList.bfsForeach(vertex -> System.out.print(vertex + " "));
    }

    /**
     * 测试基于深度优先搜索求“拓扑排序”
     */
    @Test
    public void testTopologicalSort1(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G", "H"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("B", "H"));
//        weightList.add(new Edge("H", "B"));
        weightList.add(new Edge("C", "D"));
        weightList.add(new Edge("C", "E"));
        weightList.add(new Edge("E", "F"));
        weightList.add(new Edge("E", "G"));
        weightList.add(new Edge("E", "H"));

        GraphList graphList = new GraphList(vertexArray, weightList, true);
        TopologicalSort topologicalSort = new TopologicalSort(graphList);

        topologicalSort.sortByDFS(vertex -> System.out.print(vertex + " "));
    }

    /**
     * 测试基于入度表求“拓扑排序”
     */
    @Test
    public void testTopologicalSort2(){
        //顶点
        String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G", "H"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("A", "B"));
        weightList.add(new Edge("B", "C"));
        weightList.add(new Edge("B", "H"));
//        weightList.add(new Edge("H", "B"));
        weightList.add(new Edge("C", "D"));
        weightList.add(new Edge("C", "E"));
        weightList.add(new Edge("E", "F"));
        weightList.add(new Edge("E", "G"));
        weightList.add(new Edge("E", "H"));

        GraphList graphList = new GraphList(vertexArray, weightList, true);
        TopologicalSort topologicalSort = new TopologicalSort(graphList);

        topologicalSort.sortByDegree(vertex -> System.out.print(vertex + " "));
        System.out.println();
    }

    /**
     * 测试无权图中的最短路径
     */
    @Test
    public void testUnWeightedShortPath(){
        //顶点
        String[] vertexArray = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("v1", "v2"));
        weightList.add(new Edge("v1", "v4"));
        weightList.add(new Edge("v2", "v4"));
        weightList.add(new Edge("v2", "v5"));
        weightList.add(new Edge("v3", "v1"));
        weightList.add(new Edge("v3", "v6"));
        weightList.add(new Edge("v4", "v3"));
        weightList.add(new Edge("v4", "v5"));
        weightList.add(new Edge("v4", "v6"));
        weightList.add(new Edge("v4", "v7"));
        weightList.add(new Edge("v5", "v7"));
        weightList.add(new Edge("v7", "v6"));

        GraphList graphList = new GraphList(vertexArray, weightList, true);
        ShortPath shortPath = new ShortPath(graphList);

        shortPath.unWeightedShortPath("v3", "v7");
    }

    /**
     * 测试使用 Dijkstra算法 求有权图中的最短路径
     */
    @Test
    public void testDijkstraShortPath(){
        //顶点
        String[] vertexArray = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("v1", "v2", 2));
        weightList.add(new Edge("v1", "v4", 4));
        weightList.add(new Edge("v2", "v4", 1));
        weightList.add(new Edge("v2", "v5", 5));
        weightList.add(new Edge("v3", "v1", 1));
        weightList.add(new Edge("v3", "v6", 3));
        weightList.add(new Edge("v4", "v3", 5));
        weightList.add(new Edge("v4", "v5", 3));
        weightList.add(new Edge("v4", "v6", 6));
        weightList.add(new Edge("v4", "v7", 10));
        weightList.add(new Edge("v5", "v7", 2));
        weightList.add(new Edge("v7", "v6", 1));

        GraphList graphList = new GraphList(vertexArray, weightList, true);
        ShortPath shortPath = new ShortPath(graphList);

        shortPath.dijkstraShortPath("v3", "v7");
    }

    /**
     * 测试使用 Prim算法 求有权图中的最小生成树
     */
    @Test
    public void testPrimMinSupportTree(){
        //顶点
        String[] vertexArray = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("v1", "v2", 2));
        weightList.add(new Edge("v1", "v3", 1));
        weightList.add(new Edge("v1", "v4", 4));
        weightList.add(new Edge("v2", "v4", 1));
        weightList.add(new Edge("v2", "v5", 5));
        weightList.add(new Edge("v3", "v4", 5));
        weightList.add(new Edge("v3", "v6", 3));
        weightList.add(new Edge("v4", "v5", 3));
        weightList.add(new Edge("v4", "v6", 6));
        weightList.add(new Edge("v4", "v7", 10));
        weightList.add(new Edge("v5", "v7", 2));
        weightList.add(new Edge("v6", "v7", 1));

        //无向图
        GraphList graphList = new GraphList(vertexArray, weightList);
        MinSupportTree minSupportTree = new MinSupportTree(graphList);

        minSupportTree.prim();
    }

    /**
     * 测试使用 Kruskal算法 求有权图中的最小生成树
     */
    @Test
    public void testKruskalMinSupportTree(){
        //顶点
        String[] vertexArray = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("v1", "v2", 2));
        weightList.add(new Edge("v1", "v3", 1));
        weightList.add(new Edge("v1", "v4", 4));
        weightList.add(new Edge("v2", "v4", 1));
        weightList.add(new Edge("v2", "v5", 5));
        weightList.add(new Edge("v3", "v4", 5));
        weightList.add(new Edge("v3", "v6", 3));
        weightList.add(new Edge("v4", "v5", 3));
        weightList.add(new Edge("v4", "v6", 6));
        weightList.add(new Edge("v4", "v7", 10));
        weightList.add(new Edge("v5", "v7", 2));
        weightList.add(new Edge("v6", "v7", 1));

        //无向图
        GraphList graphList = new GraphList(vertexArray, weightList);
        MinSupportTree minSupportTree = new MinSupportTree(graphList);

        minSupportTree.kruskal();
    }

    /**
     * 测试使用 Ford-Fulkerson算法 求最大流问题
     */
    @Test
    public void testFordFulkersonMaxFlow(){
        //顶点
        String[] vertexArray = {"s", "a", "b", "c", "d", "t"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("s", "a", 3));
        weightList.add(new Edge("s", "b", 2));
        weightList.add(new Edge("a", "b", 1));
        weightList.add(new Edge("a", "c", 3));
        weightList.add(new Edge("a", "d", 4));
        weightList.add(new Edge("b", "d", 2));
        weightList.add(new Edge("c", "t", 2));
        weightList.add(new Edge("d", "t", 3));

        //将有向图当做无向图处理，以满足每条流都有一个相反方向的回退流
        GraphMatrix graphMatrix = new GraphMatrix(vertexArray, weightList);
        MaxFlow maxFlow = new MaxFlow(graphMatrix);

        maxFlow.fordFulkerson("s", "t");
    }

    /**
     * 测试使用 Edmonds–Karp算法 求最大流问题
     */
    @Test
    public void testEdmondsKarpMaxFlow(){
        //顶点
        String[] vertexArray = {"s", "a", "b", "c", "d", "t"};
        //边
        List<Edge> weightList = new ArrayList<>(16);
        weightList.add(new Edge("s", "a", 3));
        weightList.add(new Edge("s", "b", 2));
        weightList.add(new Edge("a", "b", 1));
        weightList.add(new Edge("a", "c", 3));
        weightList.add(new Edge("a", "d", 4));
        weightList.add(new Edge("b", "d", 2));
        weightList.add(new Edge("c", "t", 2));
        weightList.add(new Edge("d", "t", 3));

        //这种算法不需要再额外设置回退流
        GraphMatrix graphMatrix = new GraphMatrix(vertexArray, weightList, true);
        MaxFlow maxFlow = new MaxFlow(graphMatrix);

        maxFlow.edmondsKarp("s", "t");
    }

}
